其他
30年来首次！Shor算法取得质的突破
光子盒研究院
1994年，彼得·肖尔(Peter Shor)创造了量子计算机的第一个实际用途：入侵互联网。肖尔是麻省理工学院(MIT)的一名应用数学家，他展示了量子计算机在寻找大数的素数因子方面如何能比经典计算机快出数倍。这些素数被用作密钥，确保互联网上大部分加密信息的安全。
30年来，肖尔(Shor)算法一直是量子计算机前景的一个范例。尽管当前的量子设备还不够大、也不够可靠，无法对大数进行运算。但现在，一位计算机科学家揭示了一种新的量子算法，它可能比肖尔算法更好。
纽约大学的奥德·雷格夫(Oded Regev)在8月12日首次发布在arXiv服务器上的预印本中提出了一种方案，可以大大减少超大型数字因数分解所需的门数或逻辑步骤。原则上，它可以让更小的量子计算机找出加密密钥，或者让更大的机器更快地解码加密密钥。
“这真的会产生任何影响吗？”雷杰夫表示，“我的感觉是，是的，它可能有机会。”
对这项工作进行评估的独立密码学家们也很感兴趣。麻省理工学院的计算机科学家维诺德·瓦伊昆塔纳坦(Vinod Vaikuntanathan)预计，下个月雷杰夫将就他的新算法发表学术演讲，届时将座无虚席。瓦伊昆塔纳坦说：“在量子计算的世界里，自肖尔以来的30年里，基本上只有两三个新想法出现过。你不会每天都看到这些新想法，这让我们充满希望。”杜克大学量子计算研究员肯尼思·布朗(Kenneth Brown)也同意这一观点：“因为每个人都研究肖尔算法很长时间了，这个结果令人惊讶，而且超级酷。”
与所有量子算法一样，肖尔算法依赖于量子比特的神秘特性，量子比特不仅可以设置为0和1的值，还可以同时设置为0和1的“叠加”值。少量的量子比特可以拼接成门，执行算法的逻辑运算。肖尔算法需要由n^2个门组成的量子电路，才能对n个比特长的数字进行因式分解。
目前，大多数互联网加密都依赖于至少2048位的数字：相当于十进制数字的617位。因此，用肖尔算法找到它们的质因数需要至少400万门的量子计算机，但迄今为止最大的量子计算机只有几百个量子比特。布朗说：“它们都远远达不到我们需要的规模，无法计算我们关心的数字因数。”
更糟糕的是，环境噪声经常会破坏量子比特微妙的叠加态，从而破坏运行。瓦伊昆塔纳坦认为，噪声可以通过纠错来解决，但这需要更多的量子比特——数百万甚至数十亿个量子比特。“因为纠错真的会爆炸，这就是为什么我们离真正能够计算出1000位数字的原因。改进纠错会有所帮助，但改进肖尔的算法也会有所帮助。”
雷杰夫想到了一个办法。肖尔的算法是一维的：它通过将一个数字提升到高次幂来寻找质因数，许多大数必须相乘才能得出结果。雷杰夫意识到，他可以在不同维度上对多个数字进行相乘，任何一个数字的幂次都不会太高。虽然两种算法所需的乘法总次数差不多，但雷杰夫的多维算法意味着在得出结果之前，被乘数不会变得那么大。
最终，他发现只需要n^1.5个门就能实现n位整数的因式分解。瓦伊昆塔纳坦说，这是30年来肖尔算法的首次实质性改进：“没有人真正成功过，他们都只是改进了一点点。”
但雷杰夫的算法也有缺点，瑞典政府的量子计算研究员马丁·埃克洛(Martin Ekerå)提出了这一点。
雷杰夫在试图了解其工作的实际意义时咨询过他。该算法的结构似乎需要量子存储器来存储计算过程中的中间值，这意味着需要更多（棘手的）量子比特。埃克洛说：“这就增加了算法的成本。”雷杰夫也承认人们对内存需求的担忧，但他坚持道，这种算法最终仍有可能产生价值：“也许当内存更便宜时，我们反而会担心运算的数量。”
当量子计算机准备好通过实施雷杰夫或肖尔的算法来寻找质因数时，互联网加密可能已经向前发展了。联邦机构和安全领域的领导者已经开始转向替代方案，包括所谓的 “格密码学”——它将对量子黑客攻击免疫；自2017年以来，NIST就一直与研究人员合作制定后量子密码算法的标准。即便如此，像雷杰夫和肖尔这样的算法也可以追溯应用，解密现在和不久前记录的流量，埃克洛说。
无论如何，布朗认为雷杰夫的工作纯粹是新颖的，很可能会启发和产生量子密码学领域的其他新想法，而量子密码学一直在努力寻求重大突破。“我自己也在努力思考如何进一步推动这项工作。”
参考链接：[1]https://www.science.org/content/article/surprising-and-supercool-quantum-algorithm-offers-faster-way-hack-internet-encryption[2]https://www.science.org/content/article/worried-quantum-computers-will-supercharge-hacking-white-house-calls-encryption-shift
相关阅读：NIST发布三大抗量子算法的标准草案！
量子算法能做什么、不能做什么？
迈向容错时代！Quantinuum使用逻辑量子比特实现容错算法
一文读懂量子近似优化算法(QAOA)
量子计算实际应用的利器——变分量子算法
#光子盒视频号开通啦！你要的，这里全都有#
每周一到周五，我们都将与光子盒的新老朋友相聚在微信视频号，不见不散！
|qu|cryovac>你可能会错过：|qu|cryovac>